1. Field of the Invention
This invention relates to the field of digital systems employing non-volatile memory and particularly flash memory as mass storage for computers, digital cameras and the like.
2. Description of the Prior Art
Recently, solid state memory has gained popularity for use in replacing mass storage units in various technology areas such as computers, digital cameras, modems and the like. For example, in digital cameras, the use of solid state memory, such as flash memory, replaces conventional films.
Flash memory is generally provided in the form of semiconductor devices (or chips) with each device made of a large number of transistor memory cells and each cell being individually programmable. The programming (or writing) and erasing of such a memory cell is limited to a finite number of erase-write cycles, which basically determines the lifetime of the device. Furthermore, an inherent characteristic of flash memory cells is that they must be erased and verified for successful erase prior to being programmed.
With the use of flash memory, however, the area of memory that once contained information must first be erased prior to being re-programmed. In a flash memory device, write and erase cycles are generally slow and can significantly reduce the performance of a system utilizing flash memory as its mass storage.
In applications employing flash memory devices, such as personal computers and digital cameras, a host writes and reads information to the flash memory devices through a controller device, which is commonly in the form of a semiconductor device. Such information is organized in sectors with each sector including user data information and overhead information and being generally 512 bytes in length. The controller, upon receiving sector information from the host, during a host-commanded write operation, writes the information to the flash memory devices in accordance with a predetermined sector organization. While the host may be accessing multiple sectors, each sector is written to the flash devices one at a time.
Currently, in computers wherein large files such as commercial software and user programs are stored within flash memory and in digital cameras wherein large picture files are stored within flash devices, the files are written one sector at a time within flash. Due to the latency associated with each write operation, the performance of these systems when storing large quantities of information is limited.
In storing and/or retrieving a data file (data files may be any computer files including commercial software, user program, word processor software document, spread sheet file and the like), a computer ( or host) system provides what is referred to as the logical block address indicating the location of where the host believes the data file to exist within the mass storage. The host-provided address may be in the form of cylinder, head and sector (CHS), which is converted to a logical block address format upon receipt by the controller. The same applies to digital camera applications. The controller then translates the logical block address (LBA) into a physical block address (PBA) and uses the latter to access the data file within flash memory. Each time a data file is changed, the latest version of the file is stored in an available (or `unused`) location within the flash memory that is identified by a new physical location (or new PBA). Upon using much of the free or available locations within the flash memory for updated files, an erase operation may be needed to make available `old` locations for storage of additional information. Since erase operations are time-consuming (as are write operations), there is a trade off of the frequency of performing erase operations to the time expended for searching for free locations within the flash memory as more and more locations are used prior to the next erase operation.
A variety of different algorithms may be employed for determining when an erase operation(s) will take place and as a function thereof, where within the flash memory (mass storage) the next available free block is located for storing the data file. This function is performed by the space manager unit of the controller device.
The space manager unit of the controller device maintains a table of information regarding the location of the most recent data within the flash memory in addition to the location of information that is considered `old` (information which has been superseded) and not yet erased and/or `defective` (location can not be used for storing information due to some kind of defect) or `used` (currently contains up-to-date information). This table of information is stored and updated in a volatile memory location such as RAM either within or outside of the controller device. Each time information is accessed by the host, the space manager table is used to find out the location of the information that is to be written and/or read from the flash memory devices.
An example of such a table is shown in FIG. 1 at 10 where N rows are used to store information for N number of LBAs. Each of the N rows, 12, includes a virtual PBA (VPBA) field 14, and a flag field 16. The flag field 16 comprises of an `old` flag field 18, a `used` flag field 20 and a `defect` flag field 22. The LBA is used to address a row 12 within the table 10 where a corresponding VPBA field 14 and a flag field 16 are stored. The VPBA field 14 indicates the location of a cluster, a group of blocks, within which a block of information may be located in the flash memory devices.
As shown in FIG. 1, there are N rows, one row per LBA with each LBA representing a block of information consisting of 16 sectors. That is, upon receipt of an address from the host, either in the form of CHS or LBA, the controller masks the 4 least significant bits (LSBs) of the host-provided address and shifts it to the right by 4 bits, which effectively divides the host-provided address by 16. The result of this operation is used as the LBA that points to each of the LBA rows 12 of table 10. The reason for the divide by 16 is due to a block of information stored within the flash memory devices consisting of 16 sectors. Where the flash memory devices collectively provide 32 Mbytes (each byte being 8 bits) of storage capacity, data may be organized into 4096 blocks with each block being 16 sectors. The table 10 shown in FIG. 1 will include 4096 rows (N=4096). In this respect, the entire capacity of the flash memory devices, collectively, is mapped into the rows of the table of the space manager.
Each time data, provided by the host, is to be written to the flash memory devices, a search is conducted by the space manager to find a free block, a block that is not old, used or defective.
The problem with such prior art systems is that all of the flash memory devices may have to be searched each time a free block is to be located. This approach severely effects the performance of such systems, particularly as blocks start to fill up prior to erasures thereof. To increase the frequency of erase operations, would again effect the performance of the system as erase operations are time-consuming functions.
For the foregoing reasons, there is a need within digital systems using solid state memory such as flash devices to decrease the amount of time associated with erase operations in such a way so as to increase system performance.